"""
https://leetcode.cn/problems/relative-ranks/description/

506. 相对名次
简单
相关标签
相关企业
给你一个长度为 n 的整数数组 score ，其中 score[i] 是第 i 位运动员在比赛中的得分。所有得分都 互不相同 。

运动员将根据得分 决定名次 ，其中名次第 1 的运动员得分最高，名次第 2 的运动员得分第 2 高，依此类推。运动员的名次决定了他们的获奖情况：

名次第 1 的运动员获金牌 "Gold Medal" 。
名次第 2 的运动员获银牌 "Silver Medal" 。
名次第 3 的运动员获铜牌 "Bronze Medal" 。
从名次第 4 到第 n 的运动员，只能获得他们的名次编号（即，名次第 x 的运动员获得编号 "x"）。
使用长度为 n 的数组 answer 返回获奖，其中 answer[i] 是第 i 位运动员的获奖情况。

 

示例 1：

输入：score = [5,4,3,2,1]
输出：["Gold Medal","Silver Medal","Bronze Medal","4","5"]
解释：名次为 [1st, 2nd, 3rd, 4th, 5th] 。
示例 2：

输入：score = [10,3,8,9,4]
输出：["Gold Medal","5","Bronze Medal","Silver Medal","4"]
解释：名次为 [1st, 5th, 3rd, 2nd, 4th] 。
 

提示：

n == score.length
1 <= n <= 104
0 <= score[i] <= 106
score 中的所有值 互不相同


"""
from typing import List


class Solution:
    def findRelativeRanks(self, score: List[int]) -> List[str]:
        """
        构建出idx to rank的map
        还是用归并排序
        """
        def merge(arr1:List[int],arr2:List[int])->List[List[int]]:
            res=[]
            i1=i2=0
            while i1<len(arr1) and i2<len(arr2):
                if arr1[i1]>arr2[i2]:
                    res.append(arr1[i1])
                    i1+=1
                else:
                    res.append(arr2[i2])
                    i2+=1
            while i1<len(arr1):
                res.append(arr1[i1])
                i1+=1
            while i2<len(arr2):
                res.append(arr2[i2])
                i2+=1
            return res
        
        def merge_sort(nums:List[int],left:int,right:int)->List[int]:
            if left==right-1:
                return [nums[left]]
            mid=(left+right)//2
            left_res=merge_sort(nums,left,mid)
            right_res=merge_sort(nums,mid,right)
            return merge(left_res,right_res)
        
        sort_arr=merge_sort(score,0,len(score))
        sort_map={}
        for i,val in enumerate(sort_arr):
            sort_map[val]=i

        res=[]
        medal_name=['Gold Medal','Silver Medal','Bronze Medal']
        for v in score:
            pos=sort_map[v]
            if pos<=2:
                res.append(medal_name[pos])
            else:
                res.append(str(pos+1))

        return res

if __name__=='__main__':
    sol=Solution()
    score=[10,3,8,9,4]
    res=sol.findRelativeRanks(score)
    print(res)
    pass